package com.sakura.链表;

public class Code142_环形链表II {

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    // 在环形链表的基础上，当他们相遇后，让慢指针从头开始，快慢指针再次相遇，就是环的入口结点
    /*
        理由：
            设 头到环入口点为 x，快指针到环入口为z，慢指针到环入口为y，则：
                快慢指针相遇：快指针走了 f = x + y + n * (y + z);  s = x + y
                由于快指针一次走两格，慢指针一格那么
                    2(x + y) = x + y + n * (y + z)
                    x + y = n * (y + z)
                    由于快慢指针相遇 n 必然是 大于等于 n >= 1
                    假设 当n = 1时， x = z
                    假设 当n = 2时， x = 2z
                    假设 当n = 3时， x = 3z
                    y + z 正好等于环的一圈，那么 x = n * z
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}
